package com.example.myletcodelearing.one.find


/**
 * https://offer.hi-dhl.com/#/algorithm/03-number
 * @author tgw
 * @date 2022/11/7
 * @describe https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
 *
 * 题目指出 在一个长度为 n 的数组 nums 里的所有数字都在 [0,n-1] 的范围内，可遍历数组并通过交换操作使元素的 索引 与 值，通过索引找到对应的值，算法流程如下：

当 nums[i] == i 时，即 值 和 索引，一一对应无需交换
当 nums[nums[i]] == nums[i]，即索引 nums[i] 对应的值 和 nums[i] 相等，找到相同的值，返回此值 nums[i]
上面条件都不满足，即交换索引为 i 和 nums[i] 的元素值，将数字交换到对应索引位置
没有找到返回 -1，即代表数组中无相同值
例如数组 [2,0,1] 交换逻辑如下, 当 i = 0 时：

temp = num[i], 即 temp = 2
num[i] = num[temp]，即 num[i] = 1
num[temp] = temp, 即 num[temp] = 2
将 即 值 和 索引 一一对应
 */

fun main(args: Array<String>) {
    var nums = arrayOf(1, 3, 5, 7, 9, 6, 2, 3)
//    val solution9 = Solution9.Solution().findRepeatNumber(nums)
    val solution9 = Solution9.Solution().findRepeatNumber2(nums)

    println("重复数：$solution9")

}

private class Solution9 {
    class Solution {

        //原地置换法,有问题
//        fun findRepeatNumber(nums: Array<Int>): Int {
//            for ((index, value) in nums.withIndex()) {
//                if (value == index ) continue
//                if (nums[value] == nums[index]) {
//                    return nums[index]
//                }
//                val temp = value
//                nums[index] = nums[temp]
//                nums[temp] = temp
//            }
//            return -1
//        }

        fun findRepeatNumber2(nums: Array<Int>): Int {
            var hash = HashSet<Int>()
            for (i in 0 until nums.size) {
                if (!hash.add(nums[i])){
                    return nums[i]
                }
            }
            return -1
        }
    }

}